package practise.alogrithm.gotoSiliconValley.array;

import java.util.ArrayList;
import java.util.List;

/**
 * find out the max distance of two element, the element must satisfy a[i]<a[j], i<j,
 * that's mean, find out the largest distance for a letter number larger than a previous one
 */
public class MaxIndexDistance {
    public int maxDistance(int[] array){
        List<Integer> descreaseNumbers = findOutDecreaseNumber(array);
        int maxDistance=0;
        for(int idx=0;idx<array.length;idx++){
            if(descreaseNumbers.contains(idx)){
//                should use the method below, but not the code comment out
//                for(int inner=idx;inner<array.length;inner++){
//                    if(array[idx]<array[inner] && maxDistance<inner-idx){
//                        maxDistance = inner-idx;
//                    }
//                }
                // those line is better
                for(int inner=array.length-1; inner>idx;inner--){
                    if(array[idx]<array[inner] && maxDistance<inner-idx){
                        maxDistance = inner-idx;
                    }
                }
            }
        }
        return maxDistance;
    }
    private List<Integer> findOutDecreaseNumber(int[] array){
        List<Integer> descreasedNumber = new ArrayList<>();
        descreasedNumber.add(array[0]);
        for(Integer idx=1;idx<array.length;idx++){
            if(array[idx]<descreasedNumber.get(descreasedNumber.size()-1)){
                descreasedNumber.add(idx);
            }
        }
        return descreasedNumber;
    }
}
